package main

import (
	"container/list"
	"fmt"
)

type Pair struct {
	key   int
	value int
}

type LRUCache struct {
	capacity int
	lst      *list.List
	m        map[int]*list.Element
}

func NewCacher(cap int) *LRUCache {
	return &LRUCache{
		capacity: cap,
		lst:      list.New(),
		m:        make(map[int]*list.Element, cap),
	}
}

func (lc *LRUCache) Get(key int) int {
	if ele, exist := lc.m[key]; exist {
		lc.lst.MoveToFront(ele)
		return ele.Value.(*Pair).value
	} else {
		return -1
	}
}

func (lc *LRUCache) Set(key, value int) int {
	if ele, exist := lc.m[key]; exist {
		ele.Value.(*Pair).value = value
		lc.lst.MoveToFront(ele)
		return ele.Value.(*Pair).value //返回插入的值
	} else {
		if len(lc.m) == lc.capacity { //超出缓存容量
			backEle := lc.lst.Back()
			lc.lst.Remove(backEle)                 //移除尾部元素
			delete(lc.m, backEle.Value.(*Pair).key) //删除map中对应的元素
		}
		newEle := lc.lst.PushFront(&Pair{key, value}) //插入新的元素
		lc.m[key] = newEle
		return newEle.Value.(*Pair).value
	}
}

func main() {
	lc := NewCacher(3)
	fmt.Println(lc.Get(2))     // -1
	fmt.Println(lc.Set(1, 9))  //9
	fmt.Println(lc.Set(1, 99)) //99
	fmt.Println(lc.Set(2, 8))  //8
	fmt.Println(lc.Set(3, 7))  //7
	fmt.Println(lc.Set(4, 6))  //6
	fmt.Println("-------------------")
	fmt.Println(lc.Get(4))     //6
	fmt.Println(lc.Get(3))     //7
	fmt.Println(lc.Get(2))     //8
	fmt.Println(lc.Get(1))     //-1
}
